/**
 * 
 * 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，
 * 并返回其面积。
 * rows == matrix.length
 * cols == matrix[0].length
 * 1 <= row, cols <= 200
 * matrix[i][j] 为 '0' 或 '1'
 */

 class Solution {
public:
    int largestRectangleArea(vector<int>& heights){
        stack<int> st;
        st.push(-1);
        int ans = 0;
        for(int right = 0;right < heights.size(); right++){
            int h = heights[right];
            while(st.size() > 1 and heights[st.top()] >= h){
                int i = st.top();
                st.pop();
                int left = st.top(); //栈顶下面那个数就是left
                ans = max(ans,heights[i] * (right - left - 1));
            }
            st.push(right);
        }
        return ans;
    }
    int maximalRectangle(vector<vector<char>>& matrix) {
        int n = matrix[0].size();
        vector<int> heights(n + 1);
        int ans = 0;
        for(auto& row : matrix){
            for(int j = 0;j < n;j++){
                if(row[j] == '0'){
                    heights[j] = 0; //柱子高度为0
                }else{
                    heights[j]++; //柱子高度+1
                }
            }
            ans = max(ans,largestRectangleArea(heights));
        }
        return ans;
    }
};